package leetcode.Hot100;

/**
 * @author Cheng Jun
 * Description: 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
 * <p>
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * <p>
 * 判断你是否能够到达最后一个下标。
 * @version 1.0
 * @date 2021/11/16 16:50
 * 字节面试题
 */
public class canJump {
    public static void main(String[] args) {

        System.out.println(canJump(new int[]{3, 2, 1, 0, 4}));
        System.out.println(canJump1(new int[]{3, 2, 1, 0, 4}));
        System.out.println(canJump(new int[]{0}));
        System.out.println(canJump1(new int[]{0}));
    }

    // 动态规划状态定义：dp[i] 表示能否到 下标为i 的位置
    // 动态规划初始值： dp[0] = true;
    // 动态规划转移方程：dp[i] = dp[j] && nums[j]  >= i-j
    static boolean canJump(int[] nums) {
        boolean[] dp = new boolean[nums.length];
        dp[0] = true;
        if (nums[0] >= nums.length - 1) return true;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] = dp[j] && nums[j] >= i - j;
                if (dp[i] && nums[i] >= nums.length - 1 - i) {
                    return true;
                }
                if (dp[i]) break;
            }
        }
        return dp[nums.length - 1];
    }

    // 贪心算法： nums[i] + i 表示能到达的最远下标
    static boolean canJump1(int[] nums) {
        // 能到达的最远下标
        int mostLength = nums[0] + 0;
        for (int i = 1; i < nums.length; i++) {
            // 能到达 下标i 位置就重新比较 最远距离
            if (mostLength >= i) {
                mostLength = Math.max(mostLength, i + nums[i]);
                // 能否到达数组尾下标 nums.length - 1
                if (mostLength >= nums.length - 1) return true;
            } else
                return false;
        }
        // 注意这里表示 nums 只有一个元素的情况
        return true;
    }

    static boolean canJump2(int[] nums) {
        // 2,3,1,1,4
        int length = nums.length;
        int maxDistance = 0;
        for(int i = 0; i < length; i++){
            if(maxDistance >= i){
                maxDistance = Math.max(maxDistance, nums[i] +i);
                if(maxDistance >= nums.length) return true;
            }else{
                return false;
            }
        }
        return true;
    }
}
